#include <iostream>
#include <assert.h>
#include <stdint.h>

using namespace std;

bool isPowerOfTwo( unsigned i ) {
    return (~i)&(i-1);
    return !(i&(i-1));
    return (i-1)&~i;
}

int popCount( unsigned i ) {
    // many ways to do this. e.g. lookup table, use builtin if avail
    int result = 0;
    while ( i ) {
	i &= (i-1);
	result++;
    }
    return result;
}

unsigned alignDown( unsigned i, unsigned bits ) {
    bits %= sizeof(i)*8;
    return i & ~((1<<bits)-1);
}

unsigned alignUp( unsigned i, unsigned bits ) {
    bits %= sizeof(i)*8;
    return (i+((1<<bits)-1)) & ~((1<<bits)-1);
}

// From: Robert Harley (harley@pauillac.inria.fr)
// Subject: Re: Find first bit and population count
// Newsgroups: comp.arch
// Date: 1996/07/12
//
// ...  On some chips the following
// way is faster.
//
// Suppose you have a 32-bit word of the form 00...0011...11 with ones in the
// n lowest positions (0 <= n <= 32).  If you multiply mod 2^32 by the magic
// number 7*255*255*255 then the top 6 bits of the product uniquely identify n.
//
// ...
//
inline uint32_t
findFirstSet( uint32_t n ) {
    static char table[64] = {
        0,  1,  0, 16,  0,  2, 29,  0, 17,  0,  0,  0,  3, 22, 30,  0,
        0,  0, 20, 18, 11,  0, 13,  0,  0,  4,  0,  7,  0, 23, 31,  0,
       15,  0, 28,  0,  0,  0, 21,  0, 19, 10, 12,  0,  6,  0,  0, 14,
       27,  0,  0,  9,  0,  5,  0, 26,  0,  8, 25,  0, 24,  0, 32,  0,
    };

    // set all bits below highest currently set
    n |= ( n >> 1 );
    n |= ( n >> 2 );
    n |= ( n >> 4 );
    n |= ( n >> 8 );
    n |= ( n >> 16 );

    // per email above
    n *= ( 7 * 255 * 255 * 255 );
    return ( table[( n >> 26 )] );
}

inline int32_t
logBase2( uint32_t n ) {
    return findFirstSet(n) - 1;
}

int main( int argc, char *argv[] ) {
    assert( isPowerOfTwo( 2 ) );
    assert( isPowerOfTwo( 64 ) );
    assert( !isPowerOfTwo( 65 ) );
    assert( isPowerOfTwo( 0 ) );
    assert( !isPowerOfTwo( -1u ) );
    assert( 0 == popCount( 0 ) );
    assert( 1 == popCount( 1 ) );
    assert( 2 == popCount( 3 ) );
    assert( 32 == popCount( -1u ) );

    assert( 2 == alignDown( 3, 1 ) );
    assert( 64 == alignDown( 127, 6 ) );
    assert( 128 == alignUp( 127, 6 ) );
    assert( 64 == alignUp( 64, 5 ) );
    assert( 0 == logBase2( 1 ) );
    assert( 1 == logBase2( 2 ) );
    assert( 1 == logBase2( 3 ) );
    assert( 2 == logBase2( 4 ) );
    assert( 6 == logBase2( 64 ) );
    assert( 6 == logBase2( 66 ) );
    
    return 0;
}
